/*
STL deque容器
双端数组，可以对头端进行插入和删除操作
deque 与 vector 的区别
  vector 对头部的插入、删除效率低，数据量越大，效率越低
  deque 相对而言，对头部的插入、删除效率比 vector 快
  vector 访问元素的速度比 deque 快，这和两者的内部实现有关
deque 内部工作原理
  deque 内部有个中控器，维护每段缓冲区中的内容，缓冲区中放真实数据
  中控器维护的是每个缓冲区的地址，使得使用deque是像一片连续的内存空间
deque 容器的迭代器也是支持随机访问

deque 构造函数
  deque 构造函数与 vector 一致
  函数原型
    deque<T> deq;  // 默认构造形式
    deque(initializer_list<T> il);  // 使用初始化列表 il 构造容器
    deque(beg, end);  // 将[beg, end)区间内的元素拷贝给本身
    deque(n, elem);  // 将n个elem的容器
    deque(const deque& deq);  // 拷贝构造函数

deque 赋值
  与 vector 一致
  函数原型
    deque& operator=(const deque& deq);  // 重载等号操作符
    assign(beg, end);  // 将[beg, end)区间内的数据拷贝赋值给本身
    assign(n, elem);  // 将n 个 elem 赋值给本身

deque 大小
  与 vector 相比没有capacity方法
  函数原型
    deque.empty();  // 判断容器是否为空
    deque.size();  // 返回容器中元素的个数
    deque.resize(int num);  // 重新指定容器大小 规则与 vector 一致
    deque.resize(int num, elem);  // 重新指定容器大小，用elem填充 规则与 vector 一致

deque 插入与删除
  与 vector 可以从容器头部插入与删除, 所有的pos是要迭代器的位置，不能直接写1,2,3这样的，所有容器都是！！！
  函数原型
    push_back(elem);  // 容器尾部添加数据
    push_front(elem);  // 容器头部添加数据
    pop_back();  // 删除容器最后一个数据
    pop_front();  // 删除容器第一个数据
    insert(pos, elem);  // 在指定位置插入elem, 返回新数据的位置, 也就是插入的位置
    insert(pos, n, elem); // 在指定位置插入n个elem, 无返回值
    insert(pos, beg, end);  // 在pos位置插入另一个deque[beg, end)区间内的数据， 无返回值
    erase(pos);  // 删除pos位置的数据，返回下一个数据的位置
    erase(beg, end);  // 删除[beg, end)区间内数据，返回下一个数据的位置
    clear();  // 清空容器所有数据

deque 数据存取
  与 vector 一致
  函数原型
    at(int idx);  // 返回索引idx所指数据
    operator[int idx];  // 返回索引idx所指数据
    back();  // 返回尾部元素
    front();  // 返回头部元素
   
deque 排序
  vector 也有排序 与 deque 用法一致
  函数原型
    sort(beg, end);  // 对[beg, end)区间内的元素排序

*/

#include <iostream>
#include <string>
#include <deque>
#include <algorithm>
using namespace std;

template <typename T>
void print_deq(const deque<T> &d)
{
  // for(typename deque<T>::iterator it=d.begin(); it!=d.end(); it++)  // 这种写法在这里不行 不知道为什么
  for (auto it = d.begin(); it != d.end(); it++)
    cout << *it << " ";
  cout << endl;
}

// deque 创建(构造函数)
void func1()
{
  cout << "--------------------- deque constribute -----------------" << endl;
  deque<char> d1; // deque<T> deq
  d1.push_back('a');
  d1.push_back('b');
  d1.push_back('c');
  print_deq<char>(d1);

  deque<int> d2 = {1, 2, 3};  // deque(initializer_list<T> il)
  print_deq<int>(d2);

  deque<int> d3(d2.begin(), d2.end());
  print_deq<int>(d3);

  deque<string> d4(5, "hello");
  print_deq<string>(d4);

  deque<string> d5 = d4;
  print_deq<string>(d5);
}

// deque 赋值
void func2()
{
  cout << "--------------------- deque assign -----------------" << endl;
  deque<int> d1 = {1,2,3,4};
  deque d2 = d1;
  print_deq<int>(d2);

  deque<int> d3;
  d3.assign(d2.begin(), d2.end());
  print_deq<int>(d3);

  deque<char> d4;
  d4.assign(5, 'd');
  print_deq<char>(d4);
}

// deque 大小
void func3()
{
  cout << "--------------------- deque size -----------------" << endl;
  deque<char> d1 = {'a', 'b', 'c', 'd'};
  print_deq<char>(d1);
  cout << "d1.empty: " << d1.empty() << " d1.size: "  << d1.size() << endl;

  d1.resize(10, 'f');
  cout << "d1.resize(10, 'f')" << endl;
  print_deq<char>(d1);
  cout << "d1.empty: " << d1.empty() << " d1.size: "  << d1.size() << endl;
}

// deque 插入与删除
void func4()
{
  cout << "--------------------- deque insert&erase -----------------" << endl;
  deque<int> d1={1,2,3};
  print_deq<int>(d1);
  cout << "push_back(4) push_front(0) ->";
  d1.push_back(4);
  d1.push_front(0);
  print_deq<int>(d1);

  cout << "pop_back() pop_front() -> ";
  d1.pop_back();
  d1.pop_front();
  print_deq<int>(d1);

  deque<int>::iterator pos = d1.begin();
  pos += 2;
  deque<int>::iterator res = d1.insert(pos, 9);  // res 是新数据的位置
  cout << "iterator 2 pos inert 9 -> " << *res << endl;
  print_deq<int>(d1);

  d1.insert(pos, 5, 100);
  cout << "d1.insert(pos, 5, 100) -> " << endl; 
  print_deq<int>(d1);

  res = d1.erase(pos);
  cout << "d1.erase(pos) -> size: " << d1.size() << endl;
  print_deq<int>(d1);

  res = d1.erase(pos, d1.end());
  cout << "d1.erase(pos, d1.end()) -> size: " << d1.size() << " res pos: " << *res << endl;
  print_deq<int>(d1);


  d1.clear();
  cout << "d1.clear() -> size: " << d1.size() << endl;
  print_deq<int>(d1);
}

// deque 数据存取
void func5()
{
  cout << "--------------------- deque read&write -----------------" << endl;
  deque<int> d1 = {1,2,3,4,5};
  print_deq<int>(d1);

  cout << "d1.at(1) = " << d1.at(1) << " d1[3] = " << d1[3] << endl;

  d1[2] = 100;
  d1.at(3) = 1000;
  print_deq<int>(d1);

  cout << "d1.front: " << d1.front() << " d1.back: " << d1.back() << endl;
}

// deque 排序
void func6()
{
  cout << "--------------------- deque sort -----------------" << endl;
  deque<int> d1={3,2,4,1,7,5,6};
  print_deq<int>(d1);
  sort(d1.begin(), d1.end());
  cout << "sort(d1.begin(), d1.end()) -> " << endl;
  print_deq<int>(d1);
}


int main()
{
  func1(); // deque 创建
  func2(); // deque 赋值
  func3(); // deque 大小
  func4(); // deque 插入与删除
  func5(); // deque 数据存取
  func6(); // deque 排序

  return 0;
}